This invention relates to steganography. Steganography is the art of secret communication, whose purpose is to hide the very presence of a communication. In particular this invention relates to the detection of hidden messages.
Steganography differs from cryptography, whose goal is to make communication unintelligible to those who do not posses the right keys. By means of steganography, digital images, videos, sound files, and other computer files that contain perceptually irrelevant or redundant information can be used as covers, that is, as carriers that hide secret messages embedded within. If one embeds a secret message into a cover-image, one obtains a “stego-image.”
The stego-image cannot contain any detectable artifacts that result from embedding the secret message. If it does, a third party can use such artifacts to determine that a secret message lies within the stego-image. Once the third party can reliably detect the presence of the secret message, the steganographic tool becomes useless.
Images stored in the JPEG format make very poor cover images for steganographic methods that embed information in the spatial (pixel) domain. The quantization introduced by JPEG compression can serve as a “watermark” or unique fingerprint, and one can detect even very small modifications of the cover image by inspecting the compatibility of the stego-image with the JPEG format. (See J. Fridrich, M. Goljan, and R. Du, “Steganalysis based on JPEG compatibility”, SPIE Multimedia Systems and Applications IV, Denver, Colo. (Aug. 20-24, 2001), to be presented).
Most steganographic programs use Least Significant Bit embedding (“LSB”) as the method of choice to hide a message in 24-bit and 8-bit color images, and in grayscale images. They do so because it is generally believed that changes to the LSBs of colors cannot be detected. The noise that is always present in digital images is thought to mask such changes.
The present inventors have developed a steganographic method to detect LSB embedding in 24-bit color images. (See J. Fridrich, R. Du, and L. Meng, “Steganalysis of LSB Encoding in Color Images”, ICME 2000, New York City, July 31-August 2, New York.) This RQP method is based on analyzing close pairs of colors created by LSB embedding. It works reasonably well as long as the number of unique colors in the cover image is less than 30% of the number of pixels. The size of the secret message can be estimated only very roughly. The results become progressively unreliable once the number of unique colors exceeds roughly 50% of the number of pixels, as happens frequently for high resolution raw scans and images taken with digital cameras stored in an uncompressed format. Another disadvantage of the RQP method is that it cannot be modified for grayscale images.
Westfeld and Pfitzmann (“Attacks on Steganographic Systems”, Proc. 3rd Info. Hiding Workshop, Dresden, Germany, Sep. 28-Oct. 1, 1999, pp. 61-75) introduced a method based on statistical analysis of Pairs of Values (PoVs) that are exchanged during message embedding. These PoVs could be formed, for example, by pairs of colors that differ in the LSB only. This method provides very reliable results when the message's placement is known (e.g., when it is sequential). However, randomly scattered messages can only be reliably detected with this method when the message length becomes comparable with the number of pixels in the image.
Johnson and Jajodia (“Steganography: Seeing the Unseen.” IEEE Computer, February 1998, pp.26-34; “Steganalysis of Images Created Using Current Steganography Software.” Proceedings of Workshop on Information Hiding, Portland, Oreg., April 1998. Also published as Notes in Computer Science, vol. 1525, Springer-Verlag, 1998) pointed out that steganographic methods for palette images that preprocess the palette can be vulnerable. A number of steganographic programs create clusters of close palette colors that can be swapped for each other to embed message bits. This swapping can be done by decreasing the color depth and then expanding it to 256 by making small perturbations to the colors. This preprocessing creates suspicious pairs (clusters) of colors that can be easily detected. However, steganographic techniques that do not modify the palette (e.g., those that hide messages by embedding LSB into the pointers) cannot be detected by inspecting the palette itself.
Thus there is a need for reliable and accurate steganalytic techniques that can be applied to both 24-bit color images and to 8-bit grayscale or color images with randomly scattered message bits embedded in the LSBs of colors or pointers to the palette.